/*
 * Copyright (C) 2010 Jens Bierschenk
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.googlecode.algorithmlaboratory;

import java.lang.reflect.Array;
import java.security.NoSuchAlgorithmException;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Set;

public abstract class AbstractTree<E extends Comparable<E>> implements Set<E> {
	
	protected AbstractTreeNode<E> root;
	protected int size = 0;

	/**
	 * Constructs a new, empty set, sorted according to the elements natural order.
	 */
	public AbstractTree() {}
	
	/**
	 * Constructs a new, insert with the elements of the collection, sorted according to the elements natural order.
	 * @param collection of elements, that should be insert
	 */
	public AbstractTree(Collection<E> collection) {
		this.addAll(collection);
	}
	
	@Override public abstract boolean add(E value);
	@Override public abstract boolean remove(Object object);
	
	/**
	 * Adds all of the elements in the specified collection to this set. If an element already contains in the set, 
	 * the result is false and this element is not insert. All other remaining elements are inserted.
	 * @param collection containing elements to be added to this set
	 * @return {@code true} if all elements in the specified collection insert
	 * @throws NullPointerException if the specified collection is null or if any element is null
	 */
	@Override public boolean addAll(Collection<? extends E> collection) {
		boolean result = true;
		
		if(collection == null){
			throw new NullPointerException( "The specified collection is null." );
		}
		for (E value : collection) {
			if(!add(value) && result){
				result = false;
			}
		}
		return result;
	}
	
	/**
	 * Removes all of the elements from this set. The binary tree will be empty after this call returns.
	 */
	@Override public void clear() {
		this.size = 0;
		this.root = null;
	}
	
	/**
	 * Returns {@code true} if this set contains the specified element.
	 * @param object object to be checked for containment in this set
	 * @return {@code true} if this set contains the specified element
	 * @throws NullPointerException if the specified element is null 
	 * @throws ClassCastException if the specified object cannot be compared with the elements currently in the set 
	 */
	@SuppressWarnings("unchecked")
	@Override public boolean contains(Object object) {
		return findNode((E) object) != null ? true : false;
	}
	
	/**
	 * Returns {@code true} if this set contains all of the elements of the specified collection. 
	 * If the specified collection is also a set, this method returns true if it is a subset of this set.
	 * @param collection collection to be checked for containment in this set
	 * @return {@code true} if this set contains all of the elements of the specified collection
	 * @throws NullPointerException if the specified element is null
	 * @throws ClassCastException if the specified object cannot be compared with the elements currently in the set 
	 */
	@Override public boolean containsAll(Collection<?> collection) {
		for (Object object : collection) {
			if(!contains(object)){
				return false;
			}
		}
		return true;
	}
	
	/**
	 * Returns {@code true} if this set contains no elements.
	 */
	@Override public boolean isEmpty() {
		return size() == 0;
	}
	
	/**
	 * Returns an iterator over the elements in this set in ascending order.
	 * @return an iterator over the elements in this set in ascending order
	 * @throws IllegalStateException if the next method has not yet been called
	 * @throws ConcurrentModificationException if the set is modified after instantiation the iterator
	 */
	@Override public Iterator<E> iterator() {
		return new Iterator<E>() {
			private E value;
			private int expectedSize = size;
			private AbstractTreeNode<E> next = root != null ? minimum(root) : null;

			@Override public boolean hasNext() {
				return next != null;
			}

			@Override public E next() {
				value = next.getValue();
				next = successor(findNode(value));
				return value;
			}

			@Override public void remove() {
				if(value == null){
					throw new IllegalStateException( "The next method has not yet been called." );
				}
				if(expectedSize != size){
					throw new ConcurrentModificationException( "The binary tree is modified after instantiation the iterator." );
				}
				AbstractTree.this.remove(value);
				expectedSize = size;
			}
		};
	}
	
	/**
	 * Removes all of this collection's elements that are also contained in the set.
	 * @param collection containing elements to be retained in this collection
	 * @return {@code true} if all elements of this collection removed
	 * @return {@code false} if one or mode elements of this collection not removed
	 * @throws NullPointerException if the specified element is null
	 * @throws ClassCastException if the specified object cannot be compared with the elements currently in the set
	 */
	@Override public boolean removeAll(Collection<?> collection) {
		int currentSize = size;
		for (Object object : collection) {
			remove(object);
		}
		return (currentSize - collection.size()) == size;
	}
	
	/**
	 * Retains only the elements in this set that are contained in the specified collection (optional operation). In other words, removes from this set all of its elements that are not contained in the specified collection.
	 * If the specified collection is also a set, this operation effectively modifies this set so that its value is the intersection of the two sets.
	 * 
	 * @param collection collection containing elements to be retained in this set 
	 * @return {@code true} if this set changed as a result of the call
	 * @throws NullPointerException if the specified collection is null
	 */
	@Override public boolean retainAll(Collection<?> collection) {
		int currentSize = size;
		
		if(collection == null){
			throw new NullPointerException( "The specified collection is null." );
		}
		for (E e : this) {
			if(!collection.contains(e)){
				remove(e);
			}
		}
		return currentSize != size;
	}
	
	/**
	 * Returns the number of elements in this set.
	 */
	@Override public int size() {
		return this.size;
	}
	
	/**
	 * Returns an array containing all of the elements in this set. If this set makes any guarantees as to what order its elements are returned by its iterator, 
	 * this method must return the elements in the same order.
	 * <br>
	 * The returned array will be "safe" in that no references to it are maintained by this set. (In other words, this method must allocate a new array even if this set is backed by an array).
	 * The caller is thus free to modify the returned array.
	 * @return an array containing all the elements in this set
	 */
	@Override public Object[] toArray() {
		Object[] object = new Object[ size ];
		
		int index = 0;
		for (E e : this) {
			object[index++] = e;
		}
		return object;
	}
	
	/**
	 * Returns an array containing all of the elements in this set; the runtime type of the returned array is that of the specified array. If the set fits 
	 * in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this set.
	 * <br>
	 * If this set fits in the specified array with room to spare (i.e., the array has more elements than this binary tree), the element in the array immediately following 
	 * the end of the set is binary tree to null.(This is useful in determining the length of this set only if the caller knows that this binary tree does not contain any null elements.)
	 * @param array the array into which the elements of this set are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.
	 * @return an array containing all the elements in this set
	 * @throws ArrayStoreException if the runtime type of the specified array is not a supertype of the runtime type of every element in this set
	 * @throws NullPointerException if the specified array is null
	 */
	@SuppressWarnings("unchecked")
	@Override public <T> T[] toArray(T[] array) {
		if(array == null){
			throw new NullPointerException( "The specified parameter is null." );
		}else if(array.length < size){
			array = (T[]) Array.newInstance(array.getClass().getComponentType(), size);
		}
		
		int index = 0;
		for (E e : this) {
			array[index++] = (T) e;
		}
		
		if(array.length > size){
			array[size] = null;
		}
		return array;
	}
	
	/**
	 * Returns the last (highest) element currently in this set.
	 * @return the last (highest) element currently in this set
	 * @throws NoSuchAlgorithmException if this set is empty
	 */
	public E last() throws NoSuchAlgorithmException{
		if(root == null){
			throw new NoSuchAlgorithmException( "There is no element in this binary tree." );
		}
		return maximum(root).getValue();
	}
	
	/**
	 * Returns the first (lowest) element currently in this set.
	 * @return the first (lowest) element currently in this set
	 * @throws NoSuchAlgorithmException if this set is empty
	 */
	public E first() throws NoSuchAlgorithmException{
		if(root == null){
			throw new NoSuchAlgorithmException( "There is no element in this binary tree." );
		}
		return minimum(root).getValue();
	}
	
	/**
	 * Returns the node with the smallest element in this binary tree than the given element.
	 * @param baseNode if the node is started from the off.
	 * @return {@code BinaryTreeNode} with the smallest element in this binary tree.
	 */
	private AbstractTreeNode<E> minimum(AbstractTreeNode<E> baseNode) {
		AbstractTreeNode<E> node = baseNode;
		while(node.getLeftNode() != null){
			node = node.getLeftNode();
		}
		return node;
	}
	
	/**
	 * Returns the node with the largest element in this binary tree than the given element.
	 * @param baseNode if the node is started from the off.
	 * @return {@code BinaryTreeNode} with the biggest element in this binary tree.
	 */
	private AbstractTreeNode<E> maximum(AbstractTreeNode<E> baseNode) {
		AbstractTreeNode<E> node = baseNode;
		while(node.getRightNode() != null){
			node = node.getRightNode();
		}
		return node;
	}
	
	/**
	 * Returns the successor node of the specified parameter.
	 * @param baseNode is the node that will be on the ascertainment - inorder traversal - of the successor.
	 * @return {@code BinaryTreeNode} as successor with an inorder traversal.
	 * @return {@code null} if the specified parameter the highest node in the binary tree. 
	 * @throws NullPointerException if the specified element is null.
	 */
	protected AbstractTreeNode<E> successor(AbstractTreeNode<E> baseNode){
		if(baseNode == null){
			throw new NullPointerException( "The specified parameter is null." );
		}else{
			if(baseNode.getRightNode() != null){
				return minimum(baseNode.getRightNode());
			}else{
				AbstractTreeNode<E> node = baseNode;
				AbstractTreeNode<E> parent = baseNode.getParentNode();
				
				while(parent != null && node == parent.getRightNode()){
					node = parent;
					parent = parent.getParentNode();
				}
				return parent;
			}
		}
	}
	
	/**
	 * Returns a node which includes the specified parameter.
	 * @param e to be checked for containment in this binary tree
	 * @return {@code BinaryTreeNode} if includes the specified parameter in this node
	 * @return {@code null} if no match was
	 * @throws NullPointerException if the specified element is null
	 */
	protected AbstractTreeNode<E> findNode(E e){
		AbstractTreeNode<E> node = root;
		
		if(e == null) {
			throw new NullPointerException( "The specified parameter is null." );
		}
		while(node != null){
			int cmp = e.compareTo(node.getValue());
			if( cmp == 0){
				return node;
			}else {
				node = cmp < 0 ? node.getLeftNode() : node.getRightNode();
			}
		}
		return null;
	}
}
